package com.leetcode.partition5;

/**
 * @author `RKC`
 * @date 2021/8/9 10:21
 */
public class LC416分割等和子集 {

    public static boolean canPartition(int[] nums) {
        return dynamicProgrammingImprove(nums);
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
//        int[] nums2 = {1, 2, 3, 5};
//        int[] nums2 = {1, 2, 5};
        System.out.println(canPartition(nums));
//        System.out.println(canPartition(nums2));
    }

    private static boolean dynamicProgrammingImprove(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        //是奇数时是不可能分为相等的两分
        if (sum % 2 == 1) return false;
        int capacity = sum >> 1;
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = capacity; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[capacity] == capacity;
    }

    /**
     * 背包体积：sum / 2
     * 背包要放入的商品（集合的元素）重量为元素的数值，价值也是元素的数值
     * 背包正好装满，说明找到了总和为sum / 2的子集且每个元素不可重复放入
     * 01背包的状态转移方程式：dp[i][j] = Math.max(dp[i - 1][j], values[i] + dp[i - 1][j - weight[i]])
     */
    private static boolean dynamicProgramming(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        //是奇数时是不可能分为相等的两分
        if (sum % 2 == 1) return false;
        int capacity = sum >> 1;
        //同01背包，values就是nums，weight也是nums
        int[][] dp = new int[nums.length + 1][capacity + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < nums[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
            }
        }
        for (int[] items : dp) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.printf("%-3d", items[j]);
            }
            System.out.println();
        }
        return dp[dp.length - 1][dp[0].length - 1] == capacity;
    }
}
